package mid;

/**
 在一个二维数组array中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
 [
 [1,2,8,9],
 [2,4,9,12],
 [4,7,10,13],
 [6,8,11,15]
 ]
 给定 target = 7，返回 true。

 给定 target = 3，返回 false。

 数据范围：矩阵的长宽满足 0 \le n,m \le 5000≤n,m≤500 ， 矩阵中的值满足 0 \le val \le 10^90≤val≤10
 9

 进阶：空间复杂度 O(1)O(1) ，时间复杂度 O(n+m)O(n+m)
 *
 * @author WangZhiJian
 * @since 2022/1/20
 */
public class 二维数组中的查找 {


    /**
     * 右上角
     * @param target
     * @param array
     * @return
     */
    public static boolean Find(int target, int [][] array) {
        int m = array.length;
        if (m == 0) return false;
        int n = array[0].length;
        if (n == 0) return false;
        int r = 0, c = n-1; // 右上角元素
        while (r<m && c>=0) {
            if (target == array[r][c]) {
                return true;
            }
            else if (target > array[r][c]) {
                ++r;
            }
            else {
                --c;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[][] item = new int[][]{
                new int[]{1,2,8,9}
                ,new int[]{2,4,9,12}
                ,new int[]{4,7,10,13}
                ,new int[]{6,8,11,15}
        };
        item = new int[][]{
            new int[]{1,1}
        };
        System.out.println(Find(7, item));
    }
}
